The present invention relates to monitoring of communication networks and more particularly to state information and routing table updates in large scale data networks.
In a network which comprises nodes and links between the nodes, a node is generally capable of switching connection based traffic, such as in a telephone network or an ATM (asynchronous transfer mode) network, or connectionless traffic, such as in the Internet. In a connection based network, a node may function as a switch whereas, in a connectionless inetwork, a node may function as a router.
A link may be a physical transmission medium between two nodes, for example an optical fiber, or selected wavelengths in an optical fiber. Links may have different capacities and different associated costs. As well, the number of links emanating from each node may vary from one node to another. The capacity of a link may be changed dynamically by adding channels, for instance by assigning new wavelengths in an optical network. The cost of a link may be defined according to several criteria including such qualities as reliability and delay. A directed link is a unidirectional link connecting a node X to a node Y carrying signals from node X to node Y. A node X is a neighbouring node of a node Y if a link of non-zero capacity connects node Y to node X.
A node functioning as a router determines the best route to another node based on various factors such as cost. A route is a link or a chain of links connecting a source node to a sink node. A source node is the node supporting a traffic source (the origin of the traffic) and a sink node is the node supporting a traffic sink (the destination of the traffic). Typically, a node may function as a source node and a sink node for distinct streams of traffic. A source node and a sink node form a xe2x80x9cnode pairxe2x80x9d. For a particular node pair, a route set is a number of candidate routes between the source node and the sink node that comprise the node pair. A particular route may have an associated xe2x80x9croute capacityxe2x80x9d which is equivalent to the capacity of the link with the least capacity of all links comprising the route. As well, a particular route set may have an associated xe2x80x9croute set capacityxe2x80x9d which is the sum of the capacities of the routes in a route set.
A router may maintain a set of information known about the nodes and the links in a network and may, based on this information, compute a nodal routing table comprising a route set for each possible sink node. Alternatively, network information may be maintained at a network controller where a nodal routing table for each node in the network controlled by the network controller may be created. The network controller then distributes the nodal routing table to the node to which it pertains. In an overall routing table, made up of nodal routing tables, one associated with each node, is stored a route set for each node pair in the network.
For a particular network, if the distance from some nodes in the network to the network controller is large, the network may be partitioned into sub-networks, or domains. The criteria for partitioning may be, for instance, geography. In a domain, one node can be elected to be the domain controller. Any changes in the domain can be received by the domain controller and, rather than each router computing a nodal routing table, the domain controller can compute an overall routing table and distribute a router-specific nodal routing table to each router in the domain. Nodal routing tables may be seen as columns of an overall routing table.
Proper management of a telecommunication network requires that the controller, whether centralised (network controller) or distributed (domain controller and/or router controller), be aware of the network structure and xe2x80x9cstate informationxe2x80x9d for each link. The network structure may vary due to planned addition or deletion of nodes. State information falls into two categories: functional information and traffic occupancy information. The functional state of a link normally changes very slowly with time, changing, for example, due to complete or partial failure of a node. The traffic occupancy state is a measure of the occupancy of a link, that is, the proportion of time that a link is carrying traffic. The traffic occupancy state varies more rapidly than the functional state due to the variation of temporal and spatial distribution of traffic loads. Each node in the network must be able to direct its traffic to each other node and, thus, requires network-wide state information
Any routing of traffic on the basis of fast varying traffic occupancy state information must be done with great caution since it can lead to harmful network oscillations where the end-to-end traffic carried by the network varies violently. Oscillation can occur due to large propagation delays between a point of observation or measurement and a point of control. Oscillations can be avoided, however, by ensuing that any link that is being considered for the establishment of a particular route be made unavailable for the decision process regarding the routing of any other route until a decision is made regarding the route establishment request under consideration. This process is not always easy to implement in a wide-coverage network with potentially long propagation delays. It is therefore preferable that any routing decision based on node traffic occupancy be restricted to nodes directly associated with the control element. It is also undesirable that traffic occupancy information be disseminated across the network when the propagation delay is significant. The traffic must, however, be routed on the basis of link functional availability and link functional changes must be reported network-wide. These functional changes may include capacity extension of a link and the addition of new nodes and links.
One method used widely to disseminate network state information is called xe2x80x9cfloodingxe2x80x9d, in which each node distributes link state change information to each neighbouring node. Flooding may lead to excessive transfer of redundant information. Although the information redundancy may be reduced to some extent by using a hierarchical structure for the purpose of information dissemination and routing decisions, flooding becomes awkward when the number of links per node increases. Advances in switching technology now enable the construction of large scale routers/switches with high capacity, of the order of terabits per second each, and with a large number, exceeding one hundred for example, of links. In a network deploying such nodes, an alternative to flooding is highly desirable.
Performing routing table computations in response to every link state change limits the scalability of a network. Introducing routing changes on the basis of functional network state changes must be controlled in order to avoid performing unnecessary computation for routes which are not affected by node functional state changes.
A scheme of network state monitoring and information dissemination which eliminates uncontrolled redundancy and simplifies the control protocols is desirable in order to enable network growth.
Routing traffic between a source node and a sink node in a telecommunications network can be realized using several techniques which have been extensively reported in the literature. The methods generally attempt to route traffic through the shortest available route between a source node and a sink node. Some methods, which may be classified as selective routing methods, base the route selection on the static cost of the links, the link states and the link occupancies at the time the routing decisions are made. Main considerations in devising routing methods include the computational effort required to find the favourable route and the volume of signals exchanged among the nodes.
The invention relates to the area of updating link state information across a network and the efficient utilisation of such information. In particular, the invention introduces interrelated methods for information dissemination and routing tables updates. The information dissemination method is based on periodic reporting to at least one controller, thus avoiding flooding. The method of updating the routing tables enables fast route selection decisions without resorting to running a route allocation algorithm in response to reported link state changes thereby reducing the computational effort. This is realized by predetermining a set of alternate routes for each node pair and excluding any route that includes a failed link.
In accordance with an aspect of the present invention there is provided, at a controller of a network, the network including nodes and links between the nodes, a method of disseminating link state information to the nodes, the method including ascertaining link state change information, determining a subset of nodes in the network influenced by the link state change information and indicating the link state change information to the determined subset of nodes. In another aspect of the invention a router is provided for carrying out this method. In another aspect of the invention a communication network is provided including a controller operable to carry out this method. In a further aspect of the invention a software medium permits a general purpose computer to carry out this method.
In accordance with an aspect of the present invention there is provided, at a given node in a network, the network including nodes, links between the nodes and a controller, a method of maintaining link state information, the method including receiving a nodal routing table from the controller, receiving link state change information from the controller and altering temporarily the nodal routing table based on the link state change information. In another aspect of the invention a node is provided including a processor operable to carry out this method. In a further aspect of the invention a software medium permits a general purpose computer to carry out this method.
In accordance with an aspect of the present invention there is provided a data structure for use in communicating link state change information from a sink node to a controller node including an identifier of the sink node, a message number, an indication of the number of link state changes, and for each link state change an identifier of a source node, a link state sequence number and an indication of link state change.
In accordance with an aspect of the present invention there is provided a data structure for use in communicating link state change information from a controller node to another node including an identifier of the controller node, a message number, an indication of the number of link state changes and for each link state change an identifier of a sink node, an identifier of a source node, a link state sequence number and an indication of link state change.
Other aspects and features of the present invention will become apparent to those ordinarily skilled in the art upon review of the following description of specific embodiments of the invention in conjunction with the accompanying figures.